package com.xzc.datastruc.ujava.c07._1_introduction;

/**
 * Performs the standard binary search using two comparisons per level.
 * This is a driver that calls the recursive method
 *
 * @return index where item is found or NOT_FOUND if not found
 */
public class BinarySearch {
    static int NOT_FOUND = -1;

    public static <AnyType extends Comparable<? super AnyType>>
    int binarySearch(AnyType[] a, AnyType x) {
        return binarySearch(a, x, 0, a.length - 1);
    }

    public static <AnyType extends Comparable<? super AnyType>>
    int binarySearch(AnyType[] a, AnyType x, int low, int high) {
        if (low > high)
            return NOT_FOUND;

        int mid = (low + high) / 2;

        if (a[mid].compareTo(x) < 0)
            return binarySearch(a, x, mid + 1, high);
        else if (a[mid].compareTo(x) > 0)
            return binarySearch(a, x, low, mid - 1);
        else
            return mid;
    }
}
